package com.rayboo.example.algorithm;

import java.util.Scanner;

/**
 * 二分查找
 */
public class BinarySearch {

    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
        Scanner scanner = new Scanner(System.in);
        System.out.print("输入要查找的数据：");
        int key = scanner.nextInt();
        int result = binarySearch(arr, arr.length, key);//返回数据所在位置

        if (result == -1) {
            System.out.println("你输入的数不存在数组中");
        } else {
            System.out.println("你输入的数字存在数组中的位置是：" + result);
        }
    }

    /**
     * 二分查找
     *
     * @param arr 数组
     * @param length 长度
     * @param key 输入的数
     * @return 结果
     */
    private static int binarySearch(int[] arr, int length, int key) {
        int left = 0;
        int right = length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;//未找到返回-1
    }
}
